Leetcode 321. Create Maximum Number

题目链接

Leetcode 321. Create Maximum Number

题目内容

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

Example1

Input: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 Output: [9, 8, 6, 5, 3]

Example2

Input: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 Output: [6, 7, 6, 0, 4]

Example3

Input: nums1 = [3, 9] nums2 = [8, 9] k = 3 Output: [9, 8, 9]

解题思路

本周继续我们的DP之旅，本周的题同为hard但是比之之前的要复杂一些，老样子我们先找出我们的dp状态转移方程， dp[k] = MAX(merge(maxVector1[i], maxVector2[k-i]))

有了上面的状态转移方程之后，我们就可以知道，我们需要完成maxVector, merge以及一个比较函数了，maxVector用到了类似于贪心算法的思路

当vector的size大于我们所需要的size时，如果一个数字小于它后面的一个数，后一个数往前替代他必然会使数字更大，所以直接erase它

merge则类似于归并排序，这里不多说明

比较方面也比较简单，就是按位比较两个数字，并通过判断数字的长度决定大小关系

用这种方法得出的时间复杂度较高，提交detail为

不太满意，后来经过思考发现maxVector其实很多操作是重复的，我们可以直接一次性算完单个vector对于每一种位数的max值，所以就有了第二种优化。

提交的detail为

题目代码

一开始

class Solution {
public:
    vector<int> maxVector(vector<int> nums, int k) {
        while (nums.size() > k) {
            int i = 0, n = nums.size();
            for (; i < n - 1; ++i) {
                if (nums[i] < nums[i + 1]) {
                    nums.erase(nums.begin() + i);
                    break;
                }
            }
            if (i == n - 1) nums.erase(nums.begin() + i);
        }

        return nums;
    }

    bool compare(vector<int> &nums1, int i, vector<int> &nums2, int j) {
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
            ++i;
            ++j;
        }
        if (j == nums2.size()) return true;
        if (i < nums1.size() && nums1[i] > nums2[j]) return true;
        return false;
    }

    vector<int> merge(vector<int> &nums1, vector<int> &nums2, int k) {
        vector<int> res(k, 0);
        for (int i = 0, j = 0, r = 0; r < k; ++r) {
            res[r] = compare(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
        }

        return res;
    }

    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        vector<int> res(k, 0);

        for (int i = max(0, k - n); i <= min(k, m); ++i) {
            auto v1 = maxVector(nums1, i);
            auto v2 = maxVector(nums2, k - i);
            auto tmp = merge(v1, v2, k);
            if (compare(tmp, 0, res, 0)) res = tmp;
        }

        return res;
    }
};

优化

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> result;        
        vector<vector<int>> max1 (k+1), max2(k+1);

        getMax(nums1, max1, k);
        getMax(nums2, max2, k);

        for(int i = 0; i <= k; ++i){
            if(max1[i].size() + max2[k-i].size() < k){
                continue;
            }
            mergeMax(result, max1[i], max2[k-i], k);            
        }
        return result;
    }

    void getMax(vector<int>& nums, vector<vector<int>>& max, const int k){
        int start = 0, i = 0;
        while(nums.size() > 0){
            if(nums.size() <= k){
                max[nums.size()] = nums;
            }
            for(i = start; i + 1 < nums.size() && nums[i] >= nums[i+1]; ++i);
            nums.erase(nums.begin()+i);
            start = ((i == 0) ? 0 : i-1);
        }
    }

    void mergeMax(vector<int>& result, const vector<int>& max1, const vector<int>& max2, const int k){
        vector<int> temp (k,0);
        int i = 0, j = 0;
        for( ; i < max1.size() && j < max2.size(); ){
            int ii = i;
            int jj = j;
            while(ii < max1.size() && jj < max2.size()){
                if(max1[ii] == max2[jj]){
                    ++ii; ++jj;
                }
                else break;
            }
            if((ii < max1.size() && max1[ii] > max2[jj]) || jj >= max2.size()){
                temp[i+j] = max1[i];
                ++i;
            }
            else{
                temp[i+j] = max2[j];
                ++j;
            }
        }
        for( ; i < max1.size(); ++i){
            temp[i+j] = max1[i];
        }
        for( ; j < max2.size(); ++j){
            temp[i+j] = max2[j];
        }

        if(result.empty() || smaller(result, temp)){
            result = temp;
        }
    }

    bool smaller(const vector<int>& result, const vector<int>& temp){
        for(int i = 0; i < result.size(); ++i){
            if(result[i] < temp[i])
                return true;
            if(result[i] > temp[i])
                return false;
        }
        return false;
    }
};